1. Field of the Invention
The present invention generally relates to data storage, and specifically to storage of video on a hard disk drive.
2. Background Art
Many users of satellite, cable, or even terrestrial video services have recently migrated from using analog magnetic media to record programming to digital video recorders (“DVRs”). DVRs take an input video from a video source, in digital format or in analog format by first digitizing the input video, and store the digital video on a fixed medium, such as a hard disk drive (“disk”). A user may subsequently select the recorded video for playback, record additional video, or delete the recorded video in order to free space in the disk for future recordings.
As High Definition Television (“HDTV”) standards have become more common in consumer use, DVRs have evolved to record HDTV video. HDTV video includes high resolution images that require higher data storage needs for recording. A typical 2-to-3 hour HDTV recording can occupy a 15-to-20 Gigabyte (“GB”) file.
The DVR's disk, used to store recorded content, typically includes a contiguous memory area divided into blocks. Blocks on a disk are the smallest units in which data are read from and written to the disk. In a typical disk, block sizes are small, usually around 4 kilobytes (“kB”). With a 4 kB block size, a file comprising 7 kB worth of data will consume 8 kB of disk space, because it will fully consume a 4 kB block and will consume 3 kB of a second 4 kB block. However, the remaining 1 kB on the second block cannot be used to store additional data.
In traditional filesystems, a file's structure is typically kept in an inode. The inode includes pointers to each of the blocks of data necessary to construct the file. These pointers may include a number of direct pointers, which point directly to blocks of the file's data, and some number of n-way (singly, doubly, etc.) indirect pointers. Indirect pointers are pointers that point to blocks of data that contain additional pointers. For each level of indirect access, there exists such a set of blocks of data containing additional pointers. At the final level of indirect access (the first level for indirect pointers, the second level for doubly indirect pointers, etc.), the pointers contained within the block of data are direct pointers.
Indirect pointers within an inode exist in order to allow individual files to encompass many blocks of data, and therefore allowing for very large file sizes. An inode with only direct access pointers would require the allocation, in advance, of memory for storing direct pointers to each block of data of the largest expected file size. Such an operation is wasteful when allocating smaller files. However, traversing several levels of indirection to access all of the blocks of data comprising a larger file is also expensive.
The typical 2-to-3 hour HDTV recording, occupying 15-to-20 GB of disk space, requires millions of 4 kB blocks to store the recording. Such a small block size is typically used in order to conserve space on the disk, as a 20 GB recording may consequently only waste most of a 4 kB block, an insignificant amount relative to the size of the recording. The drawback of using a small block size is, as noted, the sheer quantity of blocks needed to compose the recording.
A user desiring to delete a recording stored using a small block size may find that a typical 15-to-20 GB recording may take several minutes to delete. Prolonged deletion time can be attributed to the organization of files on a typical disk. In a traditional filesystem employing inodes as discussed above, the inode for a large recording may use a large number of n-way indirect pointers in order to provide a reference to the recording's data blocks. When deleting the recording, the filesystem has to read each pointer that points to valid data and zero them out, requiring a disk write operation to perform the zeroing. For n-way indirect pointers, the cost of accessing an additional block of data for each of the n-levels of indirection is added before being able to reach the recording's requested data block. Accordingly, the time required to perform this process is proportional to accessing the number of blocks comprising a recording times 4 bytes of data (the pointers, one per block) and writing the pointer back with a null reference.
Furthermore, as noted above, the filesystem may encounter pointers that refer to other data structures which in turn contain pointers to blocks of data in the filesystem. It may be possible for the second data structure to contain references to a third data structure, which in turn contains pointers to blocks of data in the filesystem. Such multiple levels of indirection in the filesystem generally require several seek operations by the disk in order to locate the pointed to data structure and child data structures or blocks of data. With disk seek times of a few milliseconds, accessing and zeroing all of the relevant data for a file may take 10-to-20 seconds per GB.
Accordingly, what is desired is a method for fast and efficient deletion of large files on a disk.